#include <iostream>
#include <vector>

using namespace std;

const int N = 20;

int n;
vector<int> path;
bool col[N];
//主对角线，y=x+b
bool st1[N * 2];//st1[y-x+n]，可能会出现负数，所以加上偏移量n
//副对角线，y=-x+b
bool st2[N * 2];//st2[y+x]

int cnt;

void dfs()
{
	if(path.size() == n)
	{
		if(cnt < 3)
		{
			for(auto v : path) cout << v << " ";
			cout << endl;
		}

		cnt++;
		return;
	}

	int x = path.size() + 1;
	for(int y = 1; y <= n; y++)
	{
		//判断能不能摆在这一列
		if(col[y] || st1[y-x+n] || st2[y+x]) continue;

		col[y] = st1[y-x+n] = st2[y+x] = true;
		path.push_back(y);
		dfs();

		//恢复现场
		col[y] = st1[y-x+n] = st2[y+x] = false;
		path.pop_back();
	}
}

int main()
{
	cin >> n;
	dfs();
	cout << cnt << endl;

	return 0;
}


